class Solution {
public:
    // 这种是DP，记忆化搜索，但是由于n太大了，过不了
    // vector<int> memo;
    // int dfs(int n)
    // {
    //     if(n == 1)
    //         return 0;
        
    //     if(n % 2 == 0)
    //     {
    //         if(memo[n / 2] != -1)
    //             return memo[n / 2] + 1;
    //         memo[n / 2] = dfs(n / 2);
    //         return memo[n / 2] + 1;
    //     }
    //     else
    //     {
    //         if(memo[n + 1] != -1 && memo[n - 1] != -1)
    //             return min(memo[n + 1], memo[n - 1]) + 1;
    //         memo[n + 1] = dfs(n + 1);
    //         memo[n - 1] = dfs(n - 1);
    //         return min(memo[n + 1], memo[n - 1]) + 1;
    //     }
    // }

    // int integerReplacement(int n) 
    // {
    //     memo = vector<int>(n + 2, -1);
    //     return dfs(n);
    // }

    // int integerReplacement(int n) {
    //     queue<pair<long long, int>> q;
    //     q.push(make_pair(n, 0));

    //     while (!q.empty()) {
    //         auto [current, steps] = q.front();
    //         q.pop();

    //         if (current == 1) return steps;

    //         if (current % 2 == 0) 
    //         {
    //             q.push(make_pair(current / 2, steps + 1));
    //         }
    //         else
    //         {
    //             q.push(make_pair(current + 1, steps + 1));
    //             q.push(make_pair(current - 1, steps + 1));
    //         }
    //     }
    //     return -1; // This line should never be reached
    // }

    // 广度优先搜索
    int integerReplacement(int n) 
    {
        queue<pair<long long, int>> q;
        // 优化
        unordered_set<long long> hash;
        q.push(make_pair(n, 0));
        hash.insert(n);
        while(!q.empty())
        {
            if(q.front().first == 1)
                break;
            
            if(q.front().first % 2 == 0)
            {
                if(!hash.count(q.front().first / 2))
                    q.push(make_pair(q.front().first / 2, q.front().second + 1));
            }
            else
            {
                if(!hash.count(q.front().first + 1))
                    q.push(make_pair(q.front().first + 1, q.front().second + 1));
                if(!hash.count(q.front().first - 1))
                    q.push(make_pair(q.front().first - 1, q.front().second + 1));
            }
            q.pop();
        }
        return q.front().second;
    }
};